一歩ずつ学ぶゲーム理論第1章

#一歩ずつ学ぶゲーム理論_(本)

#本（パート）

n人の戦略形ゲームをn人ゲーム(ゲーム理論)と呼ぶ，そしてそれは$ N, \left\{ S_i \right\}_{i \in N},\left\{ u_i \right\}_{i \in N}で構成される

プレイヤーの集合$ N=\left\{ 1,2,\cdots,n \right\}

プレイヤー$ iの戦略の集合 $ S_i

プレイヤーの戦略の集合の集合 $ \left\{ S_i \right\}_{i \in N}

プレイヤー$ iの利得(ゲーム理論)を定める，利得関数 $ u_i : S_1 \times \cdots \times S_n \to \mathbb{R}

プレイヤーの利得関数の集合 $ \left\{ u_i \right\}_{i \in N}

利得(ゲーム理論)は戦略の組に対して定まる

戦略に対して定まるのではない！

プレイヤー$ iが戦略$ s_iを選んだとして，その戦略の組は$ (s_1 \cdots s_i \cdots s_n)の$ n次元ベクトルとなり，これを$ sと表記することにする．

今，プレイヤー$ i以外のプレイヤーの戦略の組を，$ s_{-i}と表記する．

今，プレイヤー$ iだけが別の戦略$ s'_iに変更し，プレイヤー$ i以外は$ sから元の戦略のままとするとき，これを$ (s'_i,s_{-i})と表記する．

すなわち，$ (s'_i,s_{-i}) = (s_1 \cdots s_{i-1},s'_{i},s_{i+1} \cdots s_{n})

強支配

プレイヤー$ iの戦略$ s_i, s'_iについて，次を満たせば$ s_iが$ s'_iを強支配している．

任意のプレイヤー$ i以外の戦略の組$ s_{-i}について，$ u(s_i, s_{-i}) > u(s'_i,s_{-i})

弱支配

プレイヤー$ iの戦略$ s_i, s'_iについて，次の2条件を満たせば$ s_iが$ s'_iを弱支配している．

任意のプレイヤー$ i以外の戦略の組$ s_{-i}について$ u(s_i, s_{-i}) \geq u(s'_i,s_{-i})

少なくとも一つの戦略のプレイヤー$ i以外の戦略の組$ s_{-i}について$ u(s_i, s_{-i}) > u(s'_i,s_{-i})

戦略的同等

プレイヤー$ iの戦略$ s_i, s'_iについて，次を満たせば$ s_iと$ s'_iは戦略的同等である．

任意のプレイヤー$ i以外の戦略の組$ s_{-i}について，$ u(s_i, s_{-i}) = u(s'_i,s_{-i})

弱支配の2番目の条件が無いもの

プレイヤー$ iの戦略$ s_iが$ s'_iを強支配しているならば，$ s_iは$ s'_iを弱支配している

プレイヤー$ iの戦略$ s_iが，$ s_i以外の全ての戦略を強支配，または弱支配しているようなとき，$ s_iをプレイヤー$ iの，それぞれ強支配戦略，弱支配戦略と呼ぶ．

当然，強支配戦略なら弱支配戦略．

今後は，強支配戦略の意味で支配戦略(ゲーム理論)という言葉を使う．

プレイヤー$ iのある戦略$ s_iが戦略$ s'_iを(強，弱)支配しているならば，$ s'_iを支配された戦略と呼ぶ．

この用語は，2つではなく1つの戦略に対して呼ばれる，すなわち$ s'_iはどの戦略に支配されているかを問わず，単に支配されているということを意味している．

ゲーム理論では次のことを仮定する．

戦略A, Bのうち，BがAに強支配しているなら，プレイヤーはBを選ばない．

プレイヤーは弱支配された戦略は選ばない．

戦略$ A,Bのどちらか一方が他方を強支配も弱支配もしていなかれば，$ A,Bに支配関係がないと呼ぶ．

2人ゲームにおいて，次の解が想定される．

一方のプレイヤーに支配戦略があれば，そのプレイヤーは支配戦略を選ぶ

他方のプレイヤーは相手の支配戦略に対して，利得が一番高い戦略を選ぶ

例えば，次のようなゲームがあるとすると

table:盤面1

1\2 L R

U (2,2) (1,3)

M (1,1) (0,0)

D (0,0) (2,1)

プレイヤー1のMはUに支配されているのでMの行を削除

table:盤面2

1\2 L R

U (2,2) (1,3)

D (0,0) (2,1)

プレイヤー2のLはRに支配されているのでLの列を削除

table:盤面3

1\2 R

U (1,3)

D (2,1)

プレイヤー1のUはDに支配されているのでUの行を削除

table:盤面4

1\2 R

D (2,1)

したがって，ゲームの解は$ (D,R)．

このように強支配された戦略を削除して一つの戦略の組にたどり着かせれば，それがゲームの解として与えられる．

このようなゲームを支配可解と呼ぶ．

支配可解の数式的表現

$ n人ゲーム$ Gが与えられたとき，

$ k=0,1,\cdotsに対して，プレイヤー$ iの戦略の集合だけが異なるゲーム列$ G^k = (N, \left\{ S^k_i \right\}_{i \in N},\left\{ u_i \right\}_{i \in N})を次のように定義する．

$ k=0のとき

$ S^0_i = S_iとして，ゲーム$ G^0は元のゲーム$ Gとする

$ k\ge1のとき，

ゲーム$ G^kのプレイヤー$ iの戦略集合$ S^k_iは，ゲーム$ G^{k-1}のプレイヤー$ iの戦略集合$ S^{k-1}_iの内で強支配されない戦略の集合とする．

利得関数の定義域は元のゲーム$ Gでの利得関数の定義域の部分集合である$ S^k_1 \times \cdots \times S^k_nに制限されている．これを$ u_iの$ S^kへの制限と呼ぶ．

今，$ S_i^0 \supseteq S_i^1 \supseteq S_i^2 \cdotsであるので，ゲームの戦略集合$ S_iが有限ならば，それ以上戦略が削除できない段階$ m (m \ge 1)がある．

つまり$ mは，任意の$ k (k \ge m)に対して$ S^k = S^mを満たすような最小の数

このとき，全てのプレイヤー$ iについて$ S^m_iの要素が1つ，つまり$ S^m_i = \left\{s_i\right\}であるなら，そのゲームは支配可解であるといい，この$ (s_1,\cdots, s_n)をゲームの解とする．また，$ mは解が得られるレベルであるとよぶ．

支配可解の例

$ G^0 = (N,(S^0_1,S^0_2),(u_1,u_2))

$ S^0_1=S_1=\left\{U,M,D\right\}

$ S^0_2=S_2=\left\{L,R\right\}

table:G_0

1\2 L R

U (2,2) (1,3)

M (1,1) (0,0)

D (0,0) (2,1)

$ G^1 = (N,(S^1_1,S^1_2),(u_1,u_2))

$ S^1_1=\left\{U,D\right\}

$ S^1_2=\left\{L,R\right\}

table:G_1

1\2 L R

U (2,2) (1,3)

D (0,0) (2,1)

$ G^2 = (N,(S^2_1,S^2_2),(u_1,u_2))

$ S^2_1=\left\{U,D\right\}

$ S^2_2=\left\{R\right\}

table:G_2

1\2 R

U (1,3)

D (2,1)

$ G^3 = (N,(S^3_1,S^3_2),(u_1,u_2))

$ S^3_1=\left\{D\right\}

$ S^3_2=\left\{R\right\}

table:G_3

1\2 R

D (2,1)

したがって，ゲーム$ Gの解は$ (D,R)で，レベルは3である．

全てのプレイヤーに支配戦略があるなら，そのゲームは支配可解でレベル1である．

支配可解でないゲームについての解を考える，またはナッシュ均衡

相手の戦略に対して自分の利得を最大にする戦略を，その相手の戦略に対する最適反応戦略とよぶ．

一般に，プレイヤー$ i以外の戦略の組$ s_{-i}に対してプレイヤー$ iの戦略$ s_iが利得を最大にするなら，$ s_iを$ s_{-i}の最適反応戦略とよぶ．

より定義的には以下

プレイヤー$ iの戦略$ s_iが$ u_i(s_i,s_{-i}) = \max_{\hat{s_i} \in S_i} u_i(\hat{s_{i}},s_{-i})を満足するとき，$ s_iを$ s_{-i}の最適反応戦略とよぶ．

例えば次のとき，

table:a

1\2 A B

A (2, 4) (6, 7.5)

B (7.5, 6) (2.5, 5)

プレイヤー2のAに対するプレイヤー1の最適反応戦略はB

プレイヤー2のBに対するプレイヤー1の最適反応戦略はA

プレイヤー1のAに対するプレイヤー2の最適反応戦略はB

プレイヤー1のBに対するプレイヤー2の最適反応戦略はA

ナッシュ均衡

戦略の組$ s = (s_1, \cdots, s_n)において，全てのプレイヤー$ iの戦略$ s_iが他のプレイヤーの戦略の組$ s_{-i}に対して最適反応戦略となっているなら$ sをナッシュ均衡と呼ぶ．

ここで，上記の例

$ (A,A)はナッシュ均衡ではない．なぜならプレイヤー1のAはプレイヤー2のAに対する最適反応戦略ではない．

全プレイヤーが$ (A,A)を選択すると予測した場合，プレイヤー1は最大の利得である$ Bを選ぶ，これによって$ (A,A)が実現しなくなる．

$ (B,B)はナッシュ均衡ではない．なぜならプレイヤー1のBはプレイヤー2のBに対する最適反応戦略ではない．

一方，$ (A,B), (B,A)はナッシュ均衡．

ナッシュ均衡が複数存在することもある．

最適反応戦略の定義によってナッシュ均衡の定義を次のように言い換えることが出来る．

戦略の組$ s = (s_1, \cdots, s_n)がナッシュ均衡であるとは次のことが成り立つことと同値．

全てのプレイヤー$ iに対して，$ u_i(s) = \max_{\hat{s_i} \in S_i} u_i(\hat{s_{i}},s_{-i})

全てのプレイヤー$ iの全ての戦略$ s_i'に対して$ u_i(s) \ge u_i(s_i',s_{-i})

つまり，ナッシュ均衡であるなら，どのプレイヤーも，他のプレイヤーの戦略が変わらないならどの戦略$ s_i'に変えても利得は高くならない．

全てのプレイヤーが(弱)支配戦略を選ぶ戦略の組はナッシュ均衡．

支配可解なレベル$ mのゲーム$ Gについて，$ G^mの解はナッシュ均衡である．

全てのプレイヤーが弱支配された戦略を用いていないナッシュ均衡を支配されないナッシュ均衡と呼ぶ．

強支配された戦略はナッシュ均衡の戦略となることは出来ない．

複数あるナッシュ均衡から妥当でないものを取り除く考え方を均衡の精緻化と呼ぶ．